
#include <jni.h>
#include <string>
#include <android/log.h>
#include <queue>
#include <cmath>

using namespace std;

template<class T>
class TreeNode {
public:
    // 构造函数
    TreeNode(T data) {
        this->data = data;
    }
    T data; // 数据
    TreeNode *left = NULL;  // 左子树
    TreeNode *right = NULL; // 右子树
};

// 二叉树的深度
int getDepthTree(TreeNode<char> *pNode) {
    if (pNode == NULL) {
        return 0;
    }
    int leftDepth = getDepthTree(pNode->left); // 递归调用左节点
    int rightDepth = getDepthTree(pNode->right);
    return max(leftDepth, rightDepth) + 1; // 左右最深的，加上自己（+1）。
}

// 是否平衡二叉树。
bool isBalanceTree(TreeNode<char> *pNode) {
    // 可以是一棵空树，左右子树的高度差不会超过 1 ，并且左右两棵子树都是一棵平衡二叉树
    if (pNode == NULL) {
        return true;
    }
    // 左右子树的高度差不会超过 1
    int leftDepth = getDepthTree(pNode->left);
    int rightDepth = getDepthTree(pNode->right);

    // 并且左右两棵子树都是一棵平衡二叉树。 递归调用。abs求绝对值。
    return abs(leftDepth - rightDepth) <= 1
            && isBalanceTree(pNode->left)
            && isBalanceTree(pNode->right);
}


/**
 * 前序遍历 (必须写成模板才会通用) (方法的回调) 返回值void*visit(T)， 达到通用性。
 * 思考：CSDN 稳定性
 * void visit(T) 方法的回调。
 */
template<class T>
void preOrderTraverse(TreeNode<T> *pNode, void visit(T)) {// 怎么解决这个通用问题
    if (pNode == NULL) { // 递归到底了
        return;
    }

    // 1.首先访问根节点 自己。
    visit(pNode->data);
    // 2.然后访问左节点. 递归调用左边的节点。
    preOrderTraverse(pNode->left, visit);
    // 3.最后再去访问右子树. 递归调用右边的节点。
    preOrderTraverse(pNode->right, visit);
}

// 解决通用性问题。回调方法。
void visitNode(char data) {
    // 输出访问的点。
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "%c", data);
}

/**
 * 中序遍历
 */
template<class T>
void infixOrderTraverse(TreeNode<T> *pNode, void visit(T)) {
    if (pNode == NULL) { // 递归到底了
        return;
    }

    // 1.访问左子树：递归
    infixOrderTraverse(pNode->left, visit);
    // 2.访问根节点
    visit(pNode->data);
    // 3.访问右子树
    infixOrderTraverse(pNode->right, visit);
}

/** 后续遍历
*/
template<class T>
void epilogueOrderTraverse(TreeNode<T> *pNode, void visit(T)) {
    if (pNode == NULL) {
        return;
    }

    // 1.访问左子树：递归
    epilogueOrderTraverse(pNode->left, visit);
    // 2.访问右子树
    epilogueOrderTraverse(pNode->right, visit);
    // 3.访问根节点
    visit(pNode->data);
}

// 层序遍历: 按层顺序来遍历。ABCDEF
/**
具体步骤：借助队列来辅助。
1. A先加入队列中；
2.   再把A弹出，并访问它。访问A的左子树B、右子树C 加入队列中；
3.      然后把B弹出来，并把他的左D、右E 加入队列中；
4.      在把C推出来，并把它的左边(无左节点)、右边F 加入队列中；
5.          再推出队列中的D、E、F 。
*/
template<class T>
void levelOrderTraverse(TreeNode<T> *pNode, void visit(T)) {
    if (pNode == NULL) {
        return;
    }
    queue<TreeNode<T> *> nodeQ; // 使用队列辅助。
    nodeQ.push(pNode); // 推入根 A节点

    while (!nodeQ.empty()) { // 队列非空，一直循环。
        TreeNode<T> *front = nodeQ.front(); // 先访问
        nodeQ.pop();  // 再弹出来
        visit(front->data); // 访问节点

        if (front->left) { // 有左子树，压入队列
            nodeQ.push(front->left);
        }
        if (front->right) { // 有右子树。
            nodeQ.push(front->right);
        }
    }
}

extern "C"
JNIEXPORT jstring

JNICALL
Java_com_ndk_day42_MainActivity_stringFromJNI(
        JNIEnv *env,
        jobject /* this */) {

    // 新建节点，放入内存中。
    TreeNode<char> *A = new TreeNode<char>('A');
    TreeNode<char> *B = new TreeNode<char>('B');
    TreeNode<char> *C = new TreeNode<char>('C');
    TreeNode<char> *D = new TreeNode<char>('D');
    TreeNode<char> *E = new TreeNode<char>('E');
    TreeNode<char> *F = new TreeNode<char>('F');
    TreeNode<char> *G = new TreeNode<char>('G');

    A->left = B; // 设置A的左右子节点。
    A->right = C;

    B->left = D; // 设置B的左右子节点
    B->right = E;

    C->right = F; // 设置C的右子节点。
    // F->left = G;

    /*__android_log_print(ANDROID_LOG_ERROR,"前序遍历","%c");
    // 遍历 （前序，中序，后序，层序）
    preOrderTraverse(A, visitNode); // 把跟节点A, 传进去访问
    __android_log_print(ANDROID_LOG_ERROR,"中序遍历","%c");
    infixOrderTraverse(A, visitNode);
    __android_log_print(ANDROID_LOG_ERROR,"后序遍历","%c");
    epilogueOrderTraverse(A, visitNode);
    // 层序遍历
    __android_log_print(ANDROID_LOG_ERROR,"层序遍历","%c");
    levelOrderTraverse(A, visitNode);*/

    int depth = getDepthTree(A); // 二叉树的深度
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "depth = %d", depth); // 3
    bool isBalance = isBalanceTree(A); // 是否平衡二叉树
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "isBalanceTree = %d", isBalance);

    std::string hello = "Hello from C++";
    return env->NewStringUTF(hello.c_str());
}


